//Cracking the coding interview (5th), 1_1
//Implement an algorithm to determine if a string has all unique characters.//What if you cannot use additional data structures?
//5:23PM--5:28PM(bugfree)

//For simplicity, I assume that string is char string.
#include<bitset>
#include<string>
#include<iostream>

using namespace std;


bool all_unique(string& str) 
{
	if(str.size() > 256)
		return false;

	if(str.size() <= 1)
		return true;

	bitset<256> bs;

	for(int i = 0; i < str.size(); i++) {
		if(bs.test(str[i]))
			return false;
		else
			bs.set(str[i]);
	}

	return true;
}

int main(int argc, char *argv[]) 
{
	/** test case */
	string str("abcdefa");	/**< false */
	string str1("fedcba");	/**< true */

	bool ret = all_unique(str);
	bool ret1 = all_unique(str1);
	
	if (!ret && ret1)
		cout << "Passed test." << endl;	
	else
		cout << "Failed test." << endl;

	return 0;
}
